package com.ctrip.demo.leetcode;

import com.alibaba.fastjson.JSONObject;
import com.ctrip.demo.java8.A;
import com.google.gson.JsonObject;

import java.util.*;

public class LeetCode310 {

    public static void main(String[] args) {
        new LeetCode310().findMinHeightTrees(4, new int[][]{{1,0},{1,2},{1,3}});
    }

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {


        List<Integer> res = new ArrayList<>();
        if (n == 1) {
            res.add(0);
            return res;
        }
        // 每个节点的邻居数量
        int[] degree = new int[n];
        Map<Integer, ArrayList<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            degree[a] ++;
            degree[b] ++;
            if (map.get(a) == null) {
                // key ： 节点 value： 邻居们
                map.put(a, new ArrayList<Integer>());
            }

            if (map.get(b) == null) {
                map.put(b, new ArrayList<Integer>());
            }

            map.get(a).add(b);
            map.get(b).add(a);
        }
        System.out.println(JSONObject.toJSON(map));
        System.out.println(JSONObject.toJSON(degree));
        // 队列
        LinkedList<Integer> leafNodes = new LinkedList<>();

        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 1) {
                leafNodes.add(i);
            }
        }
        System.out.println(JSONObject.toJSON(leafNodes));

        while (leafNodes.size() > 0) {
            res.clear();
            int size = leafNodes.size();

            for (int i = 0; i < size; i++) {
                int leaf = leafNodes.poll();
                res.add(leaf);
                // 获取某个叶子节点的邻居们
                ArrayList<Integer> neighbors = map.get(leaf);
                for (Integer neighbor : neighbors) {
                    degree[neighbor]--;
                    if (degree[neighbor] == 1) {
                        leafNodes.add(neighbor);
                    }
                }
            }
        }
        return res;
    }
}
